Teorema de Turán

En teoría de grafos, El teorema de Turán es un resultado sobre en número de aristas en un grafo libre de $K_{r+1}$-clanes.

Un grafo con $n$ vértices que no contiene ningún $(r+1)$-clan puede ser formado de una partición del conjunto de vértices en $r$ partes de igual tamaño (o cuyo tamaño difiere en a lo más en un vértice), y conectando cualesquiera dos vértices pertenecientes a partes distintas. El grafo resultante es el grafo de Turán $T(n,r)$. El teorema de Turán establece que el grafo de Turán es aquel con el mayor número de aristas posible entre todos los grafos con $n$ vértices que son libres de $K_{r+1}$-clanes.

Los grafos de Turán fueron descubiertos y estudiados por el matemático húngaro Pál Turán en 1941; sin embargo, un caso especial de dicho teorema fue demostrado anteriormente por Mantel en 1907.

Enunciado del Teorema

Teorema de Turán. Sea $G$ un grafo en $n$ vértices, tal que $G$ es $K_{r+1}$-libre. Entonces, el número de aristas en G es a lo sumo

${\frac {r-1}{r}}\cdot {\frac {n^{2}}{2}}=\left(1-{\frac {1}{r}}\right)\cdot {\frac {n^{2}}{2}}.$

Una formulación equivalente es la siguiente:

Teorema de Turán (segunda formulación) De entre todos los grafos simples que son libres de $(r+1)$-clanes, $T(n,r)$ tiene el máximo número de aristas posible.

Prueba

Sea $G$ un grafo simple en $n$ vértices que no contiene $(r+1)$-clanes y que contiene el máximo número de aristas posibles.

Idea general Demostramos que un grafo en n vértices libre de $(r+1)$-clanes y con máximo número de ejes posibles tiene que ser un grafo de Turán. Por ejemplo, cuando $n=23$, para formar un grafo libre de triángulos, o 3-cliques, que maximiza el número de aristas, comenzamos por subdividir el conjunto de vértices en dos grupos $A$ y $B$ , donde $|A|=12$ y $|B|=11$. Colocamos una arista entre cualquier par vértices tales que uno está en $A$ y el otro está en $B$ pero no si ambos están en $A$ o en $B$. Por lo tanto, el número total de aristas es

$11\cdot 12=132\leq {\frac {23^{2}}{2}}\left(1-{\frac {1}{2}}\right)=132.25$

Observación 1: $G$ es un grafo completo $k$-bipartita, para algún $k<r+1$

Definimos la siguiente relación entre los vértices de $G$:

$x\sim y$ sí y sólo si $x$ no está conectado a $y$

Para demostrar esta observación, es suficiente demostrar que $\sim$ es una relación de equivalencia, ya que esto implicaría que está relación particiona los vértices de $G$ en $k$ clases de equivalencia $S_{1},\ldots ,S_{k}$ tales que ningún par de vértices dentro de la misma clase están conectados, y cualesquiera dos vértices en clases diferentes están conectados. Más aún, el subgrafo que se obtendría de escoger un vértice de cada clase de equivalencia formaría un $k$-clan, implicando que $k<r+1$. La relación es reflexiva, ya que $G$ es una gráfica simple y ningún vértice está conectado consigo mismo. Además, es claramente simétrica, por lo que sólo queda por demostrar la propiedad de transitividad.

Con el fin de llegar a una contradicción, supongamos que dicha relación no es transitiva. Entonces, hay tres vértices $u,v,w$ en la gráfica tales que $u\sim v$ y $v\sim w$, pero $u\not \sim w$. Si denotamos $d(x)$ por el grado de un vértice $x$, nos encontramos en uno de los siguientes casos:

Caso 1: $d(v)<d(u){\text{ o }}d(v)<d(w)$

Sin pérdida de generalidad, $d(v)<d(u)$. Removemos al vértice $v$ y creamos una copia del vértice $u$ (que tenga los mismos vértices adyacentes que $u$), al que llamaremos $u'$. Llamemos a esta nueva gráfica $G'$. Ya que $u\not \sim u'$, la mayor clique en $G'$ no puede tener más vértices que la mayor clique en $G$. Sin embargo, $G'$ contiene más ejes ya que:

$|E(G')|=|E(G)|-d(v)+d(u)>|E(G)|.$

lo cual contradice la maximalidad del número de aristas en $G$ como grafo $K_{r+1}$-libre.

Caso 2: $d(v)\geq d(u)$ y $d(v)\geq d(w)$

En este caso, removemos los vértices $u$ y $w$ y creamos dos copias del vértice $v$. Como en el caso 1, tenemos una contradicción, pues el grafo $G'$ que se obtiene de este proceso no puede contener $(r+1)$-clanes, pero tiene más aristas:

$|E(G')|=|E(G)|-(d(u)+d(w)-1)+2d(v)\geq |E(G)|+1.$

Ya que en cualquiera de los dos casos arriba, $G'$ contiene más aristas que $G$, obtenemos una contradicción, por lo que $\sim$ es transitiva, y concluimos que es una relación de equivalencia.

Observación 2: El número de aristas en una gráfica $k$-partita completa es maximizado cuando cualesquiera dos de las partes en que el conjunto de vértices queda subdividido difieren en tamaño en a lo más 1.

Si $G$ fuera una gráfica completa $k$-partita, con partes $A$ y $B$ tales que $|A|>|B|+1$, entonces podemos aumentar el número de aristas en $G$ trasladando un vértice de la parte $A$ a la parte $B$, y actualizando sus vértices vecinos. Al hacer esto, el grafo pierde $|B|$ aristas, pero obtiene $|A|-1$. Entonces, en total el número de aristas aumentó ya que $|A|-1-|B|\geq 1$. Con esto demostramos la segunda observación.

Observación 3: $G$ tiene que ser un grafo de Turán.

Gracias a las Observaciones 1 y 2, la única posibilidad restante de que dicho grafo $G$ maximal no sea un grafo de Turán es que tenga menos de $r$ partes. Sin embargo, en dicho caso podemos también tratar a $G$ como un grafo $r$-partita con algunas de sus partes vacías, i.e. conteniendo 0 vértices, y aplicar el mismo razonamiento de la Observación 2.

Teorema de Mantel

Este teorema es un caso especial del Teorema de Turán , cuando r = 2. Explícitamente, este es su enunciado:

Teorema de Mantel. El número máximo de aristas en un grafo libre de triángulos es $\lfloor n^{2}/4\rfloor .$ (Mantel, 1907)

En otras palabras, para obtener un grafo libre de triángulos a partir del grafo completo $K_{n}$, se deben de eliminar esencialmente la mitad de las aristas.

Una versión más fuerte del Teorema de Mantel establece que cualquier grafo Hamiltoniano con al menos $n^{2}/4$ aristas tiene que ser el grafo completo bipartita $K_{n/2,n/2}$, o de lo contrario es pancíclico; no solo contiene un triángulo, sino que además contiene ciclos de todas las posibles longitudes $1,2,\cdots ,V(G)$ (Bondy 1971).

Otra versión fuerte del teorema de Mantel establece que para cualquier grafo en $n$ vértices, este puede ser cubierto por una colección de a lo sumo $\lfloor n^{2}/4\rfloor$ clanes de tamaño 2 o 3. Un corolario de este resultado es que el número de intersecciones es a lo sumo $\lfloor n^{2}/4\rfloor$ (Erdős, Goodman y Pósa, 1966).

Referencias

• Aigner, Martin; Ziegler, Günter M. (1998), Proofs from THE BOOK, Berlín, New York: Springer-Verlag ..
• Bondy, J. Un. (1971), "Pancyclic graphs I", Bondy, J. A. (1971), «Pancyclic graphs I», Journal of Combinatorial Theory, Series B 11 (1): 80-84, doi:10.1016/0095-8956(71)90016-5 ..
• Erdős, Paul; Goodman, Un. W.; Pósa, Louis (1966), "The representation of a graph by self intersections" (PDF), Canadian Journal of Mathematics, 18 (1): 106@–112, doi:10.4153/CJM-1966-014-3, SEÑOR 0186575.
• Mantel, W. (1907), «Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff)», Wiskundige Opgaven 10: 60-61 .
• Turán, Paul (1941), «On an extremal problem in graph theory», Matematikai és Fizikai Lapok (en hungarian) 48: 436-452. .
• West, Douglas Brent (1999) [1996], Introduction to Graph Theory (2nd edición), Prentice Hall, ISBN 978-0-13-014400-3 ..

• Datos: Q1047749